package cn.walls1717.dataStructure.sort;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 类霍尔分区双边快排
 *
 * @author walls1717
 * @since 2022-04-29
 **/
public class QuickSortLikeHoare {
    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 2, 5, 2, 4};
        quickHoare(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickHoare(int[] arr, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partitionHoare(arr, l, h);
        quickHoare(arr, p + 1, h);
        quickHoare(arr, l, p - 1);
    }

    private static int partitionHoare(int[] arr, int l, int h) {
        /*
        基准点
        双边快排基准点设置在数组第一个元素
         */
        int pv = arr[l];
        // 用来从又往左遍历
        int i = l;
        // 从来从左往右遍历
        int j = h;
        /*
        双边同时循环
        当 i和j 相等的时候，证明数组遍历完毕
        结束循环
         */
        while (i < j) {
            // 右边循环，找出比基准点小的值
            while (i < j && arr[j] > pv) {
                --j;
            }
            /*
            左边循环，找出比基准点大的值
            为什么加 = ，因为如果不加 = 的话，数组中有相等的元素
            那么将会进入死循环，因为条件不成立，i指针无法移动
            当然，在 j 处加 = 效果一样
             */
            while (i < j && arr[i] <= pv) {
                ++i;
            }
            // 交换两个元素
            AlgorithmUtil.swap(arr, i, j);
        }
        /*
        结束循环后，i和j所在元素的位置，就是基准点所要在的位置
        所以，交换基准点与i或j的位置
         */
        AlgorithmUtil.swap(arr, l, j);
        // 返回基准点
        return j;
    }
}
